n=1000;
m=337;
road=[|815,28,2724|
289,887,8908|
991,24,4924|
169,328,5923|
24,624,4560|
403,97,1838|
388,126,904|
664,684,23|
754,30,2846|
526,17,7077|
904,53,4006|
389,277,9353|
698,108,5820|
384,542,2986|
345,198,8506|
633,176,4594|
229,432,2067|
24,579,1935|
444,869,3489|
199,938,129|
856,336,2222|
757,635,7341|
67,24,3828|
895,341,6173|
917,335,8480|
625,114,6322|
794,218,7426|
262,512,3228|
15,489,2214|
395,328,2058|
986,24,6014|
231,775,1171|
819,911,8425|
601,474,1085|
613,93,3966|
21,884,9136|
642,24,1799|
24,74,3272|
24,94,5794|
815,124,9382|
279,145,8162|
949,376,959|
207,24,3234|
425,186,5337|
339,548,4873|
339,421,2227|
411,774,3035|
705,787,4858|
620,933,5190|
804,589,3088|
904,68,5451|
905,443,8723|
699,975,7208|
312,609,8490|
601,980,8842|
502,676,6646|
686,11,9810|
280,934,8776|
746,576,128|
304,211,9123|
581,715,6676|
118,659,3025|
951,59,1124|
700,678,7864|
776,846,1864|
883,759,821|
87,163,1225|
325,711,525|
993,509,6496|
902,156,7454|
596,490,2197|
300,355,160|
643,703,4335|
467,41,1767|
61,350,9528|
316,605,2797|
95,955,82|
221,339,1485|
932,969,1302|
389,347,8210|
100,303,1664|
519,200,9429|
747,311,9933|
527,332,4945|
716,388,7744|
69,633,8046|
328,957,1113|
22,555,6838|
545,107,4313|
745,108,6728|
378,245,4782|
813,262,2251|
759,600,9998|
522,489,9524|
550,766,2995|
685,226,4777|
636,612,1884|
992,231,7549|
895,876,141|
368,309,1122|
33,551,9429|
272,632,6630|
809,587,3853|
752,670,6140|
765,89,3726|
317,991,933|
87,82,3762|
696,139,9951|
539,889,7451|
993,791,2832|
255,940,6899|
614,388,406|
464,392,4714|
239,293,126|
561,842,352|
57,627,6002|
718,789,1870|
805,81,337|
633,128,983|
949,654,4052|
617,155,1726|
564,217,5498|
855,238,3886|
753,855,621|
330,645,6029|
970,233,2092|
141,978,2942|
24,365,2302|
582,834,8235|
278,329,5709|
322,932,356|
887,203,4309|
392,18,3132|
547,460,1049|
940,921,656|
247,982,5378|
557,345,679|
675,920,4897|
288,927,3367|
854,901,134|
24,48,2514|
192,460,2499|
118,194,6363|
42,253,5938|
389,534,620|
741,687,695|
802,637,1149|
152,513,1454|
546,378,4923|
357,371,458|
632,833,7902|
525,536,1560|
4,832,8232|
134,642,949|
571,981,6502|
466,182,2895|
430,105,2520|
319,137,9889|
181,168,4687|
459,41,6800|
125,484,7117|
942,195,4124|
932,380,3608|
693,291,1360|
391,899,1277|
285,404,2351|
24,500,7144|
720,723,648|
727,24,1521|
213,935,6178|
24,840,8495|
256,419,6267|
57,511,1936|
117,998,3647|
802,673,8100|
976,310,1339|
618,445,6573|
604,104,9964|
20,368,6091|
760,739,1518|
357,42,6143|
961,274,880|
24,616,243|
991,489,6907|
674,231,2000|
96,806,2258|
379,204,2444|
494,1000,1788|
539,370,57|
62,455,7306|
498,948,8111|
713,51,6134|
871,784,6715|
169,29,6628|
954,232,2123|
24,373,8666|
659,893,369|
417,184,1871|
724,153,2492|
242,401,1229|
488,282,725|
193,680,609|
646,555,1395|
182,333,4693|
985,75,220|
167,953,3596|
263,685,7927|
767,380,6340|
838,24,8982|
522,516,9536|
124,409,6129|
38,862,3225|
416,24,2065|
860,471,19|
299,934,483|
48,650,836|
10,710,7645|
120,24,9145|
836,769,54|
338,695,219|
421,338,6517|
919,644,5665|
331,740,2196|
24,512,2441|
25,249,4429|
24,829,363|
343,532,4419|
7,150,2204|
88,451,9743|
140,102,9571|
790,258,515|
24,271,402|
236,377,3050|
19,716,4566|
859,44,1497|
24,345,1340|
24,111,410|
21,97,2130|
840,132,6301|
913,65,1910|
397,447,702|
312,263,2096|
660,24,295|
281,255,4263|
576,420,6522|
339,873,719|
611,337,3778|
542,73,1131|
749,672,9000|
24,51,892|
30,176,4231|
94,692,4624|
959,619,382|
691,583,4908|
622,721,6104|
380,200,3823|
201,547,4106|
618,24,5786|
859,382,8521|
224,398,3069|
397,668,6032|
166,10,6177|
924,616,7975|
100,931,6882|
275,502,4169|
426,308,7737|
340,125,5866|
138,386,4488|
793,24,1152|
173,790,693|
310,929,8317|
580,267,3288|
284,99,9342|
48,553,5604|
24,205,874|
793,511,209|
281,24,17|
492,60,2484|
999,696,457|
327,860,4313|
708,276,95|
24,706,5093|
72,981,4826|
558,24,664|
594,933,1268|
555,21,2980|
305,115,9170|
711,824,7122|
901,279,8811|
453,500,1129|
993,24,3475|
374,3,3013|
321,909,2540|
793,640,1042|
172,714,735|
708,657,708|
812,225,1737|
599,27,354|
915,53,5982|
971,78,306|
269,801,9729|
916,628,7657|
24,778,2014|
868,328,1682|
248,230,654|
777,120,350|
157,265,9212|
946,362,685|
351,803,83|
649,25,3799|
390,24,1472|
461,360,101|
608,37,1943|
400,109,4617|
287,951,1021|
802,509,7513|
806,102,7782|
814,623,467|
743,273,7065|
78,968,7913|
875,864,823|
24,215,3472|
20,116,2122|
364,850,6141|
454,65,1562|
24,736,446|
68,468,9299|
699,251,120|
95,246,7091|
480,999,960|
239,245,5422|
29,46,81|
832,782,451|
729,151,6089|
746,719,1770|
344,46,2572|
764,879,3445|
67,268,4935|
465,217,1606|
486,632,5974|
109,590,9852|
24,118,3025|
506,500,9647|
24,127,2487|
24,812,1739|
821,671,1184|
273,426,519|
24,994,1788|
796,923,7973|
36,112,1133|
457,930,1175|
428,492,6045|
42,920,6103|
47,84,438|
706,800,5559|
392,988,6139|
950,945,281|
626,892,365|
575,109,9883|
396,220,2094|
987,585,3550|
228,24,8644|
172,808,3248|
682,410,7453|
143,139,4477|
90,569,3218|
550,479,1154|
94,478,4639|
735,69,9132|
474,190,3239|
94,519,5202|
915,601,7009|
257,761,7519|
520,375,987|
743,601,750|
24,926,6968|
24,484,6428|
563,967,7768|
594,708,6512|
925,209,2456|
420,265,3881|
1,462,937|
783,154,4755|
345,591,7333|
928,860,5362|
927,77,1179|
664,792,3136|
325,678,121|
359,709,6478|
865,343,1202|
206,260,2271|
606,254,7879|
918,349,169|
989,412,8574|
701,790,86|
3,298,3951|
722,678,5799|
40,486,700|
433,598,3375|
578,867,834|
294,764,9418|
860,24,7450|
752,58,2631|
925,458,6008|
933,399,2416|
55,785,2666|
522,789,903|
887,756,5007|
810,299,387|
951,171,6194|
804,43,8752|
723,706,5302|
687,400,1448|
24,35,2501|
811,670,2933|
346,131,1865|
900,24,2993|
976,86,3155|
348,24,3535|
181,502,9247|
578,24,7732|
479,469,558|
560,480,1959|
282,24,9154|
558,342,4682|
826,878,3694|
717,690,9278|
492,934,3454|
423,584,6779|
998,472,2655|
667,76,1017|
735,820,5613|
870,879,9687|
918,381,2089|
222,789,4781|
622,181,4146|
28,529,6440|
232,169,2745|
397,676,6940|
127,699,9572|
229,360,9975|
711,621,6062|
428,919,2479|
446,383,5068|
530,578,6685|
152,461,4389|
372,541,3781|
632,5,162|
113,450,8140|
946,24,5177|
755,2,922|
181,269,8100|
891,812,2220|
9,544,1176|
695,193,3547|
782,663,5175|
886,973,3770|
629,25,5260|
774,804,730|
986,449,4963|
493,952,1088|
210,214,1826|
411,24,4605|
525,85,6633|
927,884,523|
385,898,6684|
939,911,9101|
888,135,3879|
318,58,8783|
356,220,63|
611,610,6763|
498,160,2367|
639,833,2465|
455,558,2515|
515,378,9493|
899,343,7780|
414,130,5662|
278,784,578|
984,574,7243|
101,386,2550|
283,204,858|
353,244,6062|
284,785,7723|
849,407,3616|
687,19,239|
962,450,759|
751,743,1812|
922,90,2863|
32,717,1100|
665,281,607|
979,1,2601|
237,191,2596|
861,48,4699|
313,156,8959|
24,648,19|
352,671,821|
991,135,2258|
658,826,2379|
603,679,43|
118,815,3856|
688,429,9772|
549,324,3155|
758,130,1755|
442,753,619|
884,769,5417|
387,330,2315|
758,348,7083|
303,394,117|
946,636,52|
309,204,276|
24,597,671|
75,435,2560|
16,192,5955|
851,569,710|
24,832,2921|
561,848,7851|
544,227,363|
178,70,8408|
450,371,8936|
611,24,8945|
906,241,3303|
624,47,830|
711,331,860|
264,907,327|
713,108,7752|
89,803,652|
583,227,547|
944,911,3841|
78,24,5870|
212,712,2557|
161,66,854|
806,848,1058|
702,656,2568|
331,996,1236|
83,957,882|
24,114,6985|
296,947,1766|
114,477,1692|
925,592,9095|
459,154,3880|
608,24,2662|
729,24,8546|
274,388,3289|
460,468,7989|
463,571,1921|
456,967,6793|
341,839,988|
346,306,2446|
369,717,4533|
512,568,3184|
143,728,6208|
6,460,581|
651,67,6228|
174,621,872|
74,744,9199|
707,413,2783|
843,672,7149|
291,24,8738|
773,393,2422|
319,533,94|
186,643,394|
122,475,9452|
56,702,2768|
338,54,9819|
613,831,7627|
150,24,448|
511,543,521|
827,434,1432|
580,797,4737|
780,241,8495|
361,473,7634|
462,811,988|
973,261,2525|
140,771,5686|
915,912,33|
857,24,2607|
146,517,3689|
972,611,5567|
726,817,5724|
123,913,2464|
275,666,5560|
562,200,2594|
63,235,93|
521,25,722|
24,914,6635|
712,566,5948|
301,827,5367|
763,202,6409|
762,352,9411|
181,910,459|
967,526,5442|
815,170,8251|
526,24,6222|
588,93,8606|
519,521,3044|
566,354,2094|
93,293,6540|
433,641,6361|
498,352,9993|
24,952,9356|
781,311,5697|
419,485,1116|
33,364,293|
595,26,2945|
739,384,880|
695,845,3382|
885,446,9407|
55,439,1685|
882,318,6486|
13,641,3828|
544,155,880|
491,549,9785|
786,631,3013|
179,794,2503|
10,148,7229|
993,446,3285|
535,20,8803|
847,502,2359|
164,666,370|
706,508,5536|
123,977,6658|
623,746,4984|
279,882,7888|
139,183,2416|
415,68,4033|
207,974,572|
666,581,9784|
144,840,8260|
953,844,963|
577,228,6473|
90,24,4952|
872,989,4447|
581,45,3535|
674,24,2954|
195,963,9526|
256,960,662|
828,27,728|
259,281,8555|
24,324,2859|
792,935,6463|
596,626,8142|
672,426,704|
866,669,2306|
207,61,6946|
196,278,4117|
286,818,525|
410,794,594|
875,617,3424|
363,505,692|
706,835,696|
44,169,8024|
634,332,2652|
679,19,8305|
586,108,8681|
56,724,4376|
660,941,6502|
432,943,8188|
571,680,1981|
473,597,5510|
20,334,1493|
822,85,2617|
210,616,8959|
658,956,6768|
254,496,379|
950,282,818|
471,451,1795|
827,581,2207|
656,234,5168|
147,285,668|
87,510,9517|
993,34,9246|
166,305,7990|
733,550,795|
708,64,333|
316,811,5802|
794,894,3298|
715,599,3391|
298,501,3434|
110,464,8874|
900,264,8333|
26,684,729|
635,24,2094|
323,24,2097|
250,106,4294|
807,373,2137|
216,322,4306|
628,266,2467|
190,670,7619|
905,8,2262|
534,24,5547|
66,697,7604|
529,936,90|
830,558,1590|
702,105,6692|
348,541,376|
651,252,9025|
962,483,9331|
180,440,4893|
702,12,7302|
233,902,559|
505,481,4901|
511,310,8740|
240,834,2062|
504,507,2209|
565,628,6960|
635,129,430|
592,864,6494|
24,312,4385|
279,958,3724|
434,531,4664|
179,556,4863|
395,964,1621|
457,380,1556|
311,230,8234|
661,489,5685|
947,686,420|
278,211,6001|
104,24,1100|
271,559,8823|
567,158,4386|
358,141,3512|
790,965,1756|
731,24,3404|
20,326,1038|
689,50,801|
939,209,6704|
528,96,1959|
632,116,4031|
297,239,4537|
85,647,1121|
419,799,2037|
320,194,1587|
191,484,7691|
913,909,3927|
100,903,3909|
301,843,408|
362,499,4171|
302,28,4790|
983,24,7767|
956,167,1049|
918,242,300|
581,443,5112|
79,300,10|
39,139,6703|
923,554,9762|
223,964,9644|
56,367,2908|
444,304,576|
943,704,6114|
993,257,9695|
398,495,286|
402,731,6920|
297,513,9481|
24,849,1641|
523,1000,2341|
923,271,105|
600,348,6003|
501,837,455|
495,185,1003|
87,817,8315|
536,63,2189|
917,712,9895|
754,881,1891|
662,17,893|
376,707,1669|
892,37,4175|
990,528,3097|
480,765,1540|
952,858,1409|
957,72,7218|
995,40,1261|
897,849,1039|
146,300,9438|
261,227,819|
207,866,941|
313,452,196|
574,482,8922|
114,890,9628|
14,967,6143|
339,546,944|
876,658,8756|
24,292,7651|
667,341,1102|
371,213,61|
991,537,3090|
494,379,2314|
833,344,6567|
801,38,8715|
290,4,3011|
24,503,9101|
772,219,5471|
908,979,495|
884,906,3415|
270,153,907|
417,175,8904|
149,533,7932|
712,24,2300|
717,24,8276|
24,487,2580|
260,741,6060|
855,723,8123|
96,359,7598|
267,178,2408|
838,615,6954|
841,332,1986|
24,772,290|
959,706,8118|
440,373,5755|
628,24,307|
490,763,2034|
593,82,8788|
739,448,2289|
166,572,270|
505,868,4991|
314,273,161|
409,846,5150|
465,886,4778|
694,492,1431|
195,24,9257|
470,150,8413|
843,869,1010|
906,24,5725|
877,708,4663|
909,6,2926|
519,199,6862|
658,208,9928|
580,831,7835|
592,876,317|
10,542,9575|
140,435,9182|
24,56,395|
802,427,1464|
393,306,4672|
749,732,3858|
655,565,433|
998,186,1783|
121,465,7161|
408,4,918|
819,572,5482|
160,99,7468|
46,459,388|
754,833,6789|
24,550,5268|
627,638,1301|
756,943,8136|
681,790,633|
839,524,990|
736,978,7533|
431,281,5899|
79,584,7192|
472,381,149|
899,24,5594|
5,295,9247|
898,735,7572|
158,44,8055|
182,417,2502|
178,737,4859|
552,507,8275|
937,744,2774|
500,989,8010|
353,630,7391|
896,246,2309|
874,946,5291|
702,436,1217|
573,256,1705|
107,978,5|
390,162,46|
646,607,1579|
24,189,1029|
709,294,5334|
24,794,4563|
997,596,6463|
420,654,2619|
279,418,4366|
24,311,3800|
254,476,236|
653,551,9899|
649,424,3187|
754,92,8988|
254,365,3525|
87,725,5322|
371,795,6644|
906,142,1698|
538,141,2043|
422,888,2571|
748,23,600|
498,898,7799|
49,609,4315|
822,243,1717|
825,130,577|
740,903,3296|
573,355,9579|
809,895,2475|
44,437,7233|
871,576,3160|
195,286,1982|
429,90,513|
713,482,7824|
13,24,735|
24,790,7070|
36,427,4719|
65,570,9789|
193,60,7065|
377,622,9837|
280,80,383|
24,918,8549|
386,24,8086|
397,652,221|
3,788,399|
906,366,5962|
953,31,5269|
240,244,2461|
52,78,2833|
658,220,1844|
319,750,8456|
228,734,1895|
480,805,1430|
91,291,4391|
26,161,2383|
987,943,3447|
824,750,2661|
740,98,4503|
90,163,1|
441,518,9246|
165,806,6084|
122,177,457|
966,21,9531|
197,488,7463|
705,390,891|
495,583,2412|
510,250,3544|
497,345,1336|
888,307,2462|
472,514,2998|
743,520,580|
952,507,6189|
332,578,566|
683,119,898|
947,210,5624|
315,511,8305|
466,734,8379|
345,364,3657|
960,853,48|
187,510,2414|
771,700,7432|
324,768,393|
247,511,7695|
823,363,4406|
863,923,5799|
958,146,1795|
438,24,3239|
346,631,2017|
393,816,3202|
280,880,3808|
884,188,49|
852,961,4297|
525,484,610|
798,422,2646|
24,330,556|
419,740,100|
347,59,9081|
50,587,9407|
454,23,7509|
406,731,7042|
737,913,784|
988,71,8106|
147,24,2343|
764,779,2855|
348,540,2754|
770,727,571|
99,839,7701|
480,159,586|
368,679,9880|
25,808,938|
988,24,3717|
602,330,1886|
525,370,2870|
738,51,1504|
834,211,4944|
3,433,3952|
103,650,6791|
710,997,982|
405,741,6439|
708,24,8114|
434,119,9765|
1000,139,7251|
397,441,1089|
133,438,8214|
856,24,1276|
363,677,9696|
136,480,5331|
618,742,802|
95,500,272|
958,970,3297|
445,2,455|
393,24,275|
730,321,6364|
595,167,1167|
794,122,32|];